/*
 * @lc app=leetcode.cn id=111 lang=typescript
 *
 * [111] 二叉树的最小深度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
//  思想：BFS
//  当我们找到一个叶子节点时，直接返回这个叶子节点的深度。
//  利用队列保证没有被多次访问

//  复杂度：O(n) O(n)

function minDepth(root: TreeNode | null): number {
    if (!root) return 0
    const q = []
    q.push(root)  // 将起点加入队列
    let deep = 1  // 记录扩散的步数

    while (q.length > 0) {
        const len = q.length
        /* 将当前队列中的所有节点向四周扩散 */
        for (let i = 0; i < len; i++) {
            let cur = q.shift()
            /* 划重点：这里判断是否到达终点 */
            if (cur && !cur.left && !cur.right) return deep
            /* 将 cur 的相邻节点加入队列 */
            if (cur && cur.left) q.push(cur.left)
            if (cur && cur.right) q.push(cur.right)
        }
        deep++
    }

    return deep
};
// @lc code=end

import { TreeNode } from "./type"
const root = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)))

console.log(minDepth(root));
